蟻本 2-3 01ナップサック問題

code: python

n = int(input())

w = list(map(int, input().split()))

v = list(map(int, input().split()))

W = int(input())

dp = [0 * (W + 1) for i in range(n + 1)]

for i in range(n):

for j in range(W + 1):

# ナップサックのキャパ(j)が品物のi番目の品物の重さ(wi)より小さかったら

if (j < wi):

# 入らないのでそのまま

else:

# i番目の品物が入る前の価値(dpi[j - wi])にi番目の品物の価値(vi)を足した場合と、

# i番目の品物を入れなかった場合を比較

dpi + 1j = max(dpij, dpi[j - wi] + vi)

print(dpnW)

# 4

# 2 1 3 2

# 3 2 4 2

# 5

テーマ